The present invention relates to the art of timer processing, and more particularly to a method for processing dynamically allocated timers in a real time operating system.
Most real time processing applications employ dynamically allocated timers for various purposes. In communications processing applications, for example, timers are utilized to verify that messages are processed in a reasonable amount of time. Dynamically allocated timers are activated and deactivated as the need for them arises while communications and real time data are being processed.
Dynamic timers include watchdog timers as well as timers which run to completion. Watchdog timers are started, and then generally retriggered frequently before timeout. These timers may be useful for ensuring a program or other activity performs some action before the timer expires. For example, a program may activate a watchdog timer prior to calling a subroutine, and may retrigger the watchdog timer upon return from the subroutine. If the subroutine runs normally, the watchdog is retriggered before it times out. However, if the subroutine gets caught in an endless loop situation, or otherwise does not finish in a reasonable time, the timer will time out or expire. The timer may be configured to alert the program to the excessive time taken by the subroutine or to take some other remedial action.
Other timers are started, run to completion, and then are either deactivated or restarted. These timers may be used in a program to ensure that an external event has completed. As an example, it may be desirable to read a data value from an analog to digital converter every 20 milliseconds. In this situation, a timer may be employed to notify a program to perform a data read from the converter at the expiration of a 20 millisecond timer. The timer may be restarted each time it expires in order to provide a periodic signal to the program.
Dynamically allocated timers are usually based on timing signals from clocks or other system components. A timeout duration associated with a timer may be expressed in counts, which represent an integer number of such system timing signals. For example, a microprocessor or other real time processing system may include a free running hardware timer which provides a signal to an operating system or other program, every 1 millisecond. The program may execute a timer processing routine every time the free running timer provides a signal. Timers can be activated by placing an integer count value in a memory register, representing the timer duration in milliseconds. Each time the timer service routine runs, the count values for the active timers can be decremented, and when the count value reaches zero, the timer has expired or timed out. Appropriate action can then be taken.
Several methods of processing timers have heretofore been implemented in real time processing systems. Generally, the active timers are placed into an active timer list, which may include a timer number or other identifier, a timer duration count (usually expressed as an integer), and a pointer to a service routine to be processed if and when the timer expires. The list may be unsorted or may be sorted according to duration, wherein the list must be sorted each time a new timer is activated. Whether sorted or unsorted, each time the timer processing routine runs (e.g., each time the free running timer provides a signal), the timer duration count value for each timer in the list must be decremented. If any of the count values reach zero, the timers associated therewith have timed out or expired, and the service routine associated with those timers is executed.
Where the list is unsorted, each count value in the list must be interrogated every time the timer processing routine runs, to determine if any timer has timed out. Alternatively, where the list is sorted in advance (e.g., each time a timer is added to the list) according to timer duration, only the first count value must be checked each time the timer processing routine runs. If the first count value is non-zero, no timers have timed out, and the processing is complete. However, if the first timer has timed out, the next count value in the list must be tested. This continues until a non-zero value is found, at which time the timer processing routine is finished.
Timer processing involves system overhead. Such overhead includes processing time while the timer processing routine is running, as well as when timers are added, retriggered, deleted, or when timers time out. Sorted lists require less processing overhead than unsorted lists during the timer processing routine, but involve high overhead when timers are added, because the list must be resorted. Unsorted lists require somewhat less overhead when timers are added, but greater overhead during the timer processing routine. In either case, the timer processing routine must decrement each count value entry every time the timer processing routine runs, and consequently, the processing overhead increases with the number of entries in the list.
Another previous timer processing method includes maintaining a counter which is incremented each time the timer processing routine is run. When a timer is added to the list (e.g., activated), the counted value is added to the timer duration count value for the new timer, and the result is placed in the list. Each time the timer processing routine runs, each entry in the list is compared with the current counter value, and when they are equal, the timer has timed out. This method does not require decrementing timer list entries each time the timer processing routine runs, however, the overhead is increased when timers are added to the list. Thus, conventional timer processing methods generally require greater processing time as the number of active timers increases, both during the timer processing routine, and when new timers are activated. However, it is precisely when the most timers are active, that the least timer processing overhead is desired.
Dynamically allocated timers in a real time processing environment may be of many different durations. Short duration timers are generally run to completion timers, whereas medium and long duration timers are a mix of run to completion timers and watchdog type timers. Conventional timer processing methods are somewhat efficient for handling timers of a certain duration and inefficient for other duration timers. Due to the dynamic environment of most real time processing applications, it is impossible to predict the mix of short, medium, and long duration timers which may be active at any given time. For example, in communication processing systems, messages from external devices may randomly occur in large numbers at certain times. Accordingly, conventional methods are less than optimal for efficiently processing timers in many real time applications.
In accordance with the present invention, there is provided a method of processing dynamically allocated timers in a real time processing system which requires minimal system overhead in processing both run to completion and/or watchdog type timers, of a variety of durations. The invention further provides reduced overhead associated with both timer processing routines, and with activation or addition of new timers, which is achieved for large as well as small numbers of active timers. The present invention is therefore ideally suited to real time processing applications, such as communication processing systems, wherein timers of a variety of durations are dynamically allocated randomly, and sometimes in large numbers. The invention finds further utility in association with operating systems. A method for processing dynamically allocated timers is provided, having low processing overhead for the common and frequent operations while maintaining a low and fairly constant processing overhead as the number of active timers increases.
In accordance with one aspect of the invention, separate unordered timer lists are maintained according to timer duration. This allows for the possibility of different timer processing based on the unique problems associated with timers of different duration. In this regard, one or more thresholds may be associated with a timer list, and new timers are added to the list based on a comparison of the new timer timeout duration with the threshold or thresholds associated with that list.
Another aspect of the invention provides for associating a counter with an unordered timer list. As timers are added to the list, the counter is set to the shortest duration timer in the list, and is decremented each time a timer processing routine runs. When the counter reaches zero, a timer list service task may be executed or enabled, in which the entries in the timer list are checked to determine which, if any, timers have expired or timed out. The use of the counter eliminates the need for decrementing, interrogating, comparing, or otherwise checking each list entry each time the timer processing routine runs, as was common in conventional methods. This results in decrease of the timer processing overhead incurred at each timer clock. Moreover, the overhead associated with timer processing remains low, even as the number of active timers increases. The invention thus provides the reduced overhead of a timer list having a single countdown variable as well as the reduced overhead of keeping the timers in an unordered list. The processing overhead is further reduced because the timers may be sorted into multiple lists of similar timer durations.
Still another aspect of the present invention provides for associating a scaling variable with a timer list, which is increment each time a timer processing routine is run, and which is set to zero when a timer list service task associated with the list is executed or run. Once timer entries are entered into a timer list, they are not incremented or decremented or otherwise modified, until the timer list service task runs. The scaling variable therefore represents the time since the associated timer list service task was last run, and may be used to normalize the timer timeout values relative to a known, fixed point in time. Referencing all the timers in a timer list to a fixed point in time provides for minimal overhead in adding and/or removing timers from the list.
According to yet another aspect of the invention, a method for processing timers having timer duration counts associated therewith is provided. The method comprises providing a plurality of timer lists, at least one of which having a service task, a counter, and a scaling variable associated therewith. New timers are added to one of the lists based on duration. The timer list entries are scaled based on the scaling variable, and a timer service routine is periodically executed. The service routine selectively calls, executes, or enables a timer list service task based on the counter. The method thus reduces the processing associated with prior methods and systems which required processing or servicing each entry in a timer list at each timer interrupt.
According to still another aspect of the present invention, a method is provided for processing a timer list having a service task, a counter, and timer duration counts associated therewith, comprising periodically executing a timer service routine, and selectively executing the service task based on the counter.